
public class BinTree {
	Node root;
	public void insert(int key){
		Node a_node = new Node(key);
		if (root == null){
			root = a_node;
		}else{
			Node current = root;
			Node parent;
			while (true){
				parent = current;
				if (key < current.value){
					current = current.left;
					if (current == null){
						parent.left = a_node;
						a_node.parent = parent;
						return;
					}
				}else{
					current = current.right;
					if (current == null){
						parent.right = a_node;
						a_node.parent = parent;
						return;
					}
				}
			}
		}
	}
	public Node getRoot() {
		return root;
	}
	public Node findNode(int key){
		Node current = root;
		while (current != null){
			if (key < current.value){
				current = current.left;
			}else if (key > current.value){
				current = current.right;
			}else{
				break;
			}
		}
		return current;
	}
	public Node getMininum(){
		Node current = root;
		Node last = null;
		while (current != null){
			last = current;
			current = current.left;
		}
		return last;
	}
	public Node getMaxinum(){
		Node current = root;
		Node last = null;
		while (current != null){
			last = current;
			current = current.right;
		}
		return last;
	}
	public boolean delete(int key){
		Node current = root;
		Node parent = null;
		boolean isLeftChild = false;
		while (true){
			if (current == null){
				return false;
			}else{
				if (key < current.value){
					isLeftChild = true;
					parent = current;
					current = current.left;
				}else if (key > current.value){
					isLeftChild = false;
					parent = current;
					current = current.right;
				}else{
					//find, parent == null if be deleted is ROOT
					break;
				}
			}
		}
		current.parent = null; //disconnect it from its parent
		//current node need be delete
		if (current.left == null && current.right == null){ //No children, it's a leaf.
			if (current  == root){
				root = null;
			}else if (isLeftChild){
				parent.left = null;
			}else {
				parent.right = null;
			}
		}else if (current.left == null){
			if (current == root){
				root = current.right;
			}else if(isLeftChild){
				parent.left = current.right;
				if (parent.left != null){
					parent.left.parent = parent;
				}
			}else{
				parent.right = current.right;
				if (parent.right != null){
					parent.right.parent = parent;
				}
			}
		}else if (current.right == null){
			if (current == root)
				root = current.left;
			else if (isLeftChild){
				parent.left = current.left;
				if (parent.left != null){
					parent.left.parent = parent;
				}
			}
			else{
				parent.right = current.left;
				if (parent.right != null){
					parent.right.parent = parent;
				}
			}
		}else{ //left, right is not null
			Node successor = findSuccessor(current);
			if (current == null){
				root = successor;
			}else if (isLeftChild){
				parent.left = successor;
				parent.left.parent = parent;
			}else{
				parent.right = successor;
				parent.right.parent = parent;
			}
			current.left.parent = successor;
			successor.left = current.left;
			
		}
		return true;
	}
	private Node findSuccessor(Node node) {
		Node successorParent,successor,current;
		successorParent = node;
		successor = node;
		current = node.right;
		while (current != null){
			successorParent = successor;
			successor = current;
			current = current.left;
		}
		if (successor != node.right){
			successorParent.left = successor.right;
			if (successorParent.left != null){
				successorParent.left.parent = successorParent;
			}
			successor.right = node.right;
			if (successor.right != null){
				successor.right.parent = successor;
			}
		}
		return successor;
	}
	
}
